//
//  XBBFSExample.c
//  数据结构算法和笔试题
//
//  Created by 王国栋 on 16/6/23.
//  Copyright © 2016年 xiaobai. All rights reserved.
//

#include "XBBFSExample.h"


// --- 

// 广度优先搜索借助的是队列

/*
 
 */

// 代码来自啊哈算

// 小哼通过秘密的方法得到了一张不完整的钓鱼岛的航拍地图，钓鱼岛由一个主岛和一些附属岛屿组成，小哼决定去钓鱼岛探险，下面这个10＊10的二维矩阵就是钓鱼岛的航拍地图，途中的数字表示海拔，0表示海洋，1-9表示的是陆地，
// 小哼的飞机最终会降落（6，8）处，现在需要统计，小哼落地所在的岛屿的面积，此处把小哼降落点上下左右相连接的陆地均视为同一个岛屿
/*
 10 10 6 8
 
 1 2 1 0 0 0 0 0 2 3
 
 3 0 2 0 1 2 1 0 1 2
 
 4 0 1 0 1 2 3 2 0 1
 
 3 2 0 0 0 1 2 4 0 0
 
 0 0 0 0 0 0 1 5 3 0
 
 0 1 2 1 0 1 5 4 3 0
 
 0 1 2 3 1 3 6 2 1 0
 
 0 0 3 4 8 9 7 5 0 0
 
 0 0 0 3 7 8 6 0 1 2
 
 0 0 0 0 0 0 0 0 1 0
 
 */
//解决思路就是在 （6，8）开始进行广度优先搜索，每次需要向上下左右四个方向扩展，当扩展出的点大于
//0的时候就加入队列，直到队列扩展完毕，所有加入队列的点的总数就是小岛的面积
#include <stdio.h>
struct note
{
    int x;
    int y;
};
int Find()
{
    struct note que[2501];
    int head,tail;
    int book[51][51]={0};
    int a[51][51];
    int i,j,k,sum=0,n,m,startx,starty,tx,ty;
    int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
    scanf("%d %d %d %d",&n,&m,&startx,&starty);
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    head=1;
    tail=1;
    //initailize queue
    que[tail].x=startx;
    que[tail].y=starty;
    tail++;
    book[startx][starty]=1;
    sum=1;
    
    //while the queue is not empty ,do the loop
    while (head<tail)
    {
        for(k=0;k<=3;k++)
        {
            tx=que[head].x+next[k][0];
            ty=que[head].y+next[k][1];
            if(tx<1||tx>n||ty<1||ty>m)
                continue;
            if (a[tx][ty]>0&&book[tx][ty]==0)
            {
                sum++;
                //each point insert the queue one time,so book the point has  been inserted
                book[tx][ty]=1;
                que[tail].x=tx;
                que[tail].y=ty;
                tail++;
                
            }
            
        }
        head++;
    }
    
    printf("%d",sum);
    getchar();
    getchar();
    return 0;
}

/*
 
 最少转机－－－图的广度优先遍历
 
 5 7 1 5
 
 1 2
 
 1 3
 
 2 3
 
 2 4
 
 3 4
 
 3 5
 
 4 5
 
 第一行的5表示有5个城市，城市编号1-5，7表示有7条路线，1表示起点城市，5表示目标城市，接下来的七行没行是一条类似“a b“这样的数据
 
 表示的城市a和城市b之间的航线，也就是a和b之间时可以到达的.
 
 要求转站次数最少，可以认为所有的图的边的值是1。
 
 广度优先搜索更加适用于所有边的权制相同的情况
 */


 
/*
 
#include <stdio.h>
#include <stdlib.h>
#define M 99999999
struct note
{
    int x;//城市编号
    int s;//转机次数
};
int main(int argc, const char * argv[]) {
    struct  note que[2501];
    int e[51][51]={0},book[51]={0};
    int head,tail;
    int i,j,n,m,a,b,cur,start,end,flag=0;
    for (i=1; i<=m; i++) {
        
        for (j=1; j<=n; j++) {
            if(i==j)
                e[i][j]=0;
            else
                e[i][j]=M;
        }
        
        
    }
    for (i=1; i<=n; i++) {
        scanf("%d %d",&a,&b);
        e[a][b]=1;
        e[b][a]=1;//表示是可以联通的。
    }
    head=1;
    tail=1;
    que[tail].x=start;
    que[tail].s=0;
    book[start]=1;//标记start号已经在队里里面
    tail++;
    while (head<tail) {
        cur=que[head].x;
        for (j=1; j<=n; j++) {
            if (e[cur][j]!=M&&book[j]==0)
            {
                que[tail].x=j;
                que[tail].s=que[head].s+1;
                tail++;
                book[j]=1;
            }
            if (que[tail-1].x==end) {
                flag=1;
                break;
            }
        }
        if (flag) {
            break;
        }
        head++;
    }
    printf("%d",que[tail-1].s);
    return 0;
}

 */














